package com.gitee.wsl.func.filter.bloomfilter.bean

import com.gitee.wsl.text.format.format
import kotlin.math.*

/**
 * The definition of a Bloom filter shape.
 *
 *
 * This class contains the values for the filter configuration and is used to
 * convert a Hasher into a BloomFilter as well as verify that two Bloom filters are
 * compatible. (i.e. can be compared or merged)
 *
 * <h2>Interrelatedness of values</h2>
 *
 * <dl>
 * <dt>Number of Items (`n`)</dt>
 * <dd>`n = ceil(m / (-k / ln(1 - exp(ln(p) / k))))`</dd>
 * <dt>Probability of False Positives (`p`)</dt>
 * <dd>`p = pow(1 - exp(-k / (m / n)), k)`</dd>
 * <dt>Number of Bits (`m`)</dt>
 * <dd>`m = ceil((n * ln(p)) / ln(1 / pow(2, ln(2))))`</dd>
 * <dt>Number of Functions (`k`)</dt>
 * <dd>`k = round((m / n) * ln(2))`</dd>
</dl> *
 *
 * <h2>Estimations from cardinality based on shape</h2>
 *
 *
 * Several estimates can be calculated from the Shape and the cardinality of a Bloom filter.
 *
 *
 * In the calculation below the following values are used:
 *
 *  * double c = the cardinality of the Bloom filter.
 *  * double m = numberOfBits as specified in the shape.
 *  * double k = numberOfHashFunctions as specified in the shape.
 *
 *
 * <h3>Estimate N - n()</h3>
 *
 *
 * The calculation for the estimate of N is: `-(m/k) * ln(1 - (c/m))`.  This is the calculation
 * performed by the `Shape.estimateN(cardinality)` method below.  This estimate is roughly equivalent to the
 * number of hashers that have been merged into a filter to create the cardinality specified.
 *
 *
 * *Note:*
 *
 *  * if cardinality == numberOfBits, then result is infinity.
 *  * if cardinality &gt; numberOfBits, then result is NaN.
 *
 *
 * <h3>Estimate N of Union - n(A  B)</h3>
 *
 *
 * To estimate the number of items in the union of two Bloom filters with the same shape, merge them together and
 * calculate the estimated N from the result.
 *
 * <h3>Estimate N of the Intersection - n(A  B)</h3>
 *
 *
 * To estimate the number of items in the intersection of two Bloom filters A and B with the same shape the calculation is:
 * n(A) + n(b) - n(A  B).
 *
 *
 * Care must be taken when any of the n(x) returns infinity.  In general the following assumptions are true:
 *
 *
 *  * If n(A) =  and n(B) &lt;  then n(A  B) = n(B)
 *  * If n(A) &lt;  and n(B) =  then n(A  B) = n(A)
 *  * If n(A) =  and n(B) =  then n(A  B) =
 *  * If n(A) &lt;  and n(B) &lt;  and n(A  B) =  then n(A  B) is undefined.
 *
 *
 * @see [Bloom Filter calculator](https://hur.st/bloomfilter)
 *
 * @see [Bloom filter
 * [Wikipedia]](https://en.wikipedia.org/wiki/Bloom_filter)
 *
 * @since 4.5.0-M1
 */
class Shape private constructor(
    numberOfHashFunctions: Int,
    numberOfBits: Int
) {
    /**
     * Gets the number of hash functions used to construct the filter.
     * This is also known as `k`.
     *
     * @return the number of hash functions used to construct the filter (`k`).
     */
    /**
     * Number of hash functions to create a filter (`k`).
     */
    val numberOfHashFunctions: Int = checkNumberOfHashFunctions(numberOfHashFunctions)

    /**
     * Gets the number of bits in the Bloom filter.
     * This is also known as `m`.
     *
     * @return the number of bits in the Bloom filter (`m`).
     */
    /**
     * Number of bits in the filter (`m`).
     */
    val numberOfBits: Int = checkNumberOfBits(numberOfBits)

    override fun equals(other: Any?): Boolean {
        // Shape is final so no check for the same class as inheritance is not possible
        if (other is Shape) {
            val other = other
            return numberOfBits == other.numberOfBits && numberOfHashFunctions == other.numberOfHashFunctions
        }
        return false
    }

    /**
     * Estimates the maximum number of elements that can be merged into a filter of
     * this shape before the false positive rate exceeds the desired rate.
     *
     * The
     * formula for deriving `k` when `m` and `n` are known is:
     *
     *
     * `k = ln2 * m / n`
     *
     *
     * Solving for `n` yields:
     *
     *
     * `n = ln2 * m / k`
     *
     * @return An estimate of max N.
     */
    fun estimateMaxN(): Double {
        return numberOfBits * LN_2 / numberOfHashFunctions
    }

    /**
     * Estimate the number of items in a Bloom filter with this shape and the specified number of bits enabled.
     *
     *
     * *Note:*
     *
     *  *  if cardinality == numberOfBits, then result is infinity.
     *  *  if cardinality &gt; numberOfBits, then result is NaN.
     *
     *
     * @param cardinality the number of enabled  bits also known as the hamming value.
     * @return An estimate of the number of items in the Bloom filter.
     */
    fun estimateN(cardinality: Int): Double {
        val c = cardinality.toDouble()
        val m = numberOfBits.toDouble()
        val k = numberOfHashFunctions.toDouble()
        return -(m / k) * ln1p(-c / m)
    }

    /**
     * Calculates the probability of false positives (`p`) given
     * numberOfItems (`n`), numberOfBits (`m`) and numberOfHashFunctions (`k`).
     * <pre>p = pow(1 - exp(-k / (m / n)), k)</pre>
     *
     *
     * This is the probability that a Bloom filter will return true for the presence of an item
     * when it does not contain the item.
     *
     *
     * The probability assumes that the Bloom filter is filled with the expected number of
     * items. If the filter contains fewer items then the actual probability will be lower.
     * Thus, this returns the worst-case false positive probability for a filter that has not
     * exceeded its expected number of items.
     *
     * @param numberOfItems the number of items hashed into the Bloom filter.
     * @return the probability of false positives.
     */
    fun getProbability(numberOfItems: Int): Double {
        require(numberOfItems >= 0) { "Number of items must be greater than or equal to 0: $numberOfItems" }
        if (numberOfItems == 0) {
            return 0.0
        }
        return (-expm1(-1.0 * numberOfHashFunctions * numberOfItems / numberOfBits)).pow(numberOfHashFunctions.toDouble())
    }

    override fun hashCode(): Int {
        // Match Arrays.hashCode(new int[] {numberOfBits, numberOfHashFunctions})
        return (31 + numberOfBits) * 31 + numberOfHashFunctions
    }

    /**
     * Determines if a cardinality is sparse based on the shape.
     *
     * This method assumes that bit maps are 64bits and indexes are 32bits. If the memory
     * necessary to store the cardinality as indexes is less than the estimated memory for bit maps,
     * the cardinality is determined to be `sparse`.
     *
     * @param cardinality the cardinality to check.
     * @return true if the cardinality is sparse within the shape.
     */
    fun isSparse(cardinality: Int): Boolean {
        /*
                 * Since the size of a bit map is a long and the size of an index is an int,
                 * there can be 2 indexes for each bit map. In Bloom filters indexes are evenly
                 * distributed across the range of possible values, Thus if the cardinality
                 * (number of indexes) is less than or equal to 2*number of bit maps the
                 * cardinality is sparse within the shape.
                 */

        return cardinality <= BitMaps.numberOfBitMaps(this) * 2
    }

    override fun toString(): String {
        return String.format("Shape[k=%s m=%s]", numberOfHashFunctions, numberOfBits)
    }

    companion object {
        /**
         * The natural logarithm of 2. Used in several calculations. Approximately 0.693147180559945.
         */
        private val LN_2 = ln(2.0)

        /**
         * ln(1 / 2^ln(2)). Used in calculating the number of bits. Approximately -0.480453013918201.
         *
         *
         * ln(1 / 2^ln(2)) = ln(1) - ln(2^ln(2)) = -ln(2) * ln(2)
         */
        private val DENOMINATOR = -LN_2 * LN_2

        /**
         * Calculates the number of hash functions given numberOfItems and numberOfBits.
         * This is a method so that the calculation is consistent across all constructors.
         *
         * @param numberOfItems the number of items in the filter.
         * @param numberOfBits the number of bits in the filter.
         * @return the optimal number of hash functions.
         * @throws IllegalArgumentException if the calculated number of hash function is `< 1`
         */
        private fun calculateNumberOfHashFunctions(numberOfItems: Int, numberOfBits: Int): Int {
            // k = round((m / n) * ln(2)) We change order so that we use real math rather
            // than integer math.
            val k: Long = round(LN_2 * numberOfBits / numberOfItems).toLong()
            require(k >= 1) {
                String.format("Filter too small: Calculated number of hash functions (%s) was less than 1", k)
            }
            // Normally we would check that numberOfHashFunctions <= Integer.MAX_VALUE but
            // since numberOfBits is at most Integer.MAX_VALUE the numerator of
            // numberOfHashFunctions is ln(2) * Integer.MAX_VALUE = 646456992.9449 the
            // value of k cannot be above Integer.MAX_VALUE.
            return k.toInt()
        }

        /**
         * Checks the calculated probability is `< 1.0`.
         *
         *
         *
         * This function is used to verify that the dynamically calculated probability for the Shape is in the valid range 0 to 1 exclusive. This need only be
         * performed once upon construction.
         *
         *
         * @param probability the probability
         * @throws IllegalArgumentException if the probability is `>= 1.0`.
         */
        private fun checkCalculatedProbability(probability: Double) {
            // We do not need to check for p <= 0.0 since we only allow positive values for
            // parameters and the closest we can come to exp(-kn/m) == 1 is
            // exp(-1/Integer.MAX_INT) approx 0.9999999995343387 so Math.pow(x, y) will
            // always be 0<x<1 and y>0
            require(!(probability >= 1.0)) { "Calculated probability is greater than or equal to 1: $probability" }
        }

        /**
         * Checks number of bits is strictly positive.
         *
         * @param numberOfBits the number of bits
         * @return the number of bits
         * @throws IllegalArgumentException if the number of bits is `< 1`.
         */
        private fun checkNumberOfBits(numberOfBits: Int): Int {
            require(numberOfBits >= 1) { "Number of bits must be greater than 0: $numberOfBits" }
            return numberOfBits
        }

        /**
         * Checks number of hash functions is strictly positive.
         *
         * @param numberOfHashFunctions the number of hash functions
         * @return the number of hash functions
         * @throws IllegalArgumentException if the number of hash functions is `< 1`.
         */
        private fun checkNumberOfHashFunctions(numberOfHashFunctions: Int): Int {
            require(numberOfHashFunctions >= 1) { "Number of hash functions must be greater than 0: $numberOfHashFunctions" }
            return numberOfHashFunctions
        }

        /**
         * Checks number of items is strictly positive.
         *
         * @param numberOfItems the number of items
         * @return the number of items
         * @throws IllegalArgumentException if the number of items is `< 1`.
         */
        private fun checkNumberOfItems(numberOfItems: Int): Int {
            require(numberOfItems >= 1) { "Number of items must be greater than 0: $numberOfItems" }
            return numberOfItems
        }

        /**
         * Checks the probability is in the range 0.0, exclusive, to 1.0, exclusive.
         *
         * @param probability the probability
         * @throws IllegalArgumentException if the probability is not in the range `(0, 1)`
         */
        private fun checkProbability(probability: Double) {
            // Using the negation of within the desired range will catch NaN
            require(probability > 0.0 && probability < 1.0) { "Probability must be greater than 0 and less than 1: $probability" }
        }

        /**
         * Constructs a filter configuration with the specified number of hashFunctions (`k`) and
         * bits (`m`).
         *
         * @param numberOfHashFunctions Number of hash functions to use for each item placed in the filter.
         * @param numberOfBits The number of bits in the filter
         * @return a valid Shape.
         * @throws IllegalArgumentException if `numberOfHashFunctions < 1` or `numberOfBits < 1`
         */
        fun fromKM(numberOfHashFunctions: Int, numberOfBits: Int): Shape {
            return Shape(numberOfHashFunctions, numberOfBits)
        }

        /**
         * Constructs a filter configuration with the specified number of items (`n`) and
         * bits (`m`).
         *
         *
         * The optimal number of hash functions (`k`) is computed.
         * <pre>k = round((m / n) * ln(2))</pre>
         *
         *
         * The false-positive probability is computed using the number of items, bits and hash
         * functions. An exception is raised if this is greater than or equal to 1 (i.e. the
         * shape is invalid for use as a Bloom filter).
         *
         * @param numberOfItems Number of items to be placed in the filter
         * @param numberOfBits The number of bits in the filter
         * @return a valid Shape.
         * @throws IllegalArgumentException if `numberOfItems < 1`, `numberOfBits < 1`,
         * the calculated number of hash function is `< 1`, or if the actual probability is `>= 1.0`
         */
        fun fromNM(numberOfItems: Int, numberOfBits: Int): Shape {
            checkNumberOfItems(numberOfItems)
            checkNumberOfBits(numberOfBits)
            val numberOfHashFunctions = calculateNumberOfHashFunctions(numberOfItems, numberOfBits)
            val shape = Shape(numberOfHashFunctions, numberOfBits)
            // check that probability is within range
            checkCalculatedProbability(shape.getProbability(numberOfItems))
            return shape
        }

        /**
         * Constructs a filter configuration with the specified number of items, bits
         * and hash functions.
         *
         *
         * The false-positive probability is computed using the number of items, bits and hash
         * functions. An exception is raised if this is greater than or equal to 1 (i.e. the
         * shape is invalid for use as a Bloom filter).
         *
         * @param numberOfItems Number of items to be placed in the filter
         * @param numberOfBits The number of bits in the filter.
         * @param numberOfHashFunctions The number of hash functions in the filter
         * @return a valid Shape.
         * @throws IllegalArgumentException if `numberOfItems < 1`, `numberOfBits < 1`,
         * `numberOfHashFunctions < 1`, or if the actual probability is `>= 1.0`.
         */
        fun fromNMK(numberOfItems: Int, numberOfBits: Int, numberOfHashFunctions: Int): Shape {
            checkNumberOfItems(numberOfItems)
            checkNumberOfBits(numberOfBits)
            checkNumberOfHashFunctions(numberOfHashFunctions)
            // check that probability is within range
            val shape = Shape(numberOfHashFunctions, numberOfBits)
            // check that probability is within range
            checkCalculatedProbability(shape.getProbability(numberOfItems))
            return shape
        }

        /**
         * Constructs a filter configuration with the specified number of items (`n`) and
         * desired false-positive probability (`p`).
         *
         *
         * The number of bits (`m`) for the filter is computed.
         * <pre>m = ceil(n * ln(p) / ln(1 / 2^ln(2)))</pre>
         *
         *
         * The optimal number of hash functions (`k`) is computed.
         * <pre>k = round((m / n) * ln(2))</pre>
         *
         *
         * The actual probability will be approximately equal to the
         * desired probability but will be dependent upon the calculated number of bits and hash
         * functions. An exception is raised if this is greater than or equal to 1 (i.e. the
         * shape is invalid for use as a Bloom filter).
         *
         * @param numberOfItems Number of items to be placed in the filter
         * @param probability The desired false-positive probability in the range `(0, 1)`
         * @return a valid Shape
         * @throws IllegalArgumentException if `numberOfItems < 1`, if the desired probability
         * is not in the range `(0, 1)` or if the actual probability is `>= 1.0`.
         */
        fun fromNP(numberOfItems: Int, probability: Double): Shape {
            checkNumberOfItems(numberOfItems)
            checkProbability(probability)

            // Number of bits (m)
            val m = ceil(numberOfItems * ln(probability) / DENOMINATOR)
            require(!(m > Int.MAX_VALUE)) { "Resulting filter has more than " + Int.Companion.MAX_VALUE + " bits: " + m }
            val numberOfBits = m.toInt()

            val numberOfHashFunctions = calculateNumberOfHashFunctions(numberOfItems, numberOfBits)
            val shape = Shape(numberOfHashFunctions, numberOfBits)
            // check that probability is within range
            checkCalculatedProbability(shape.getProbability(numberOfItems))
            return shape
        }

        /**
         * Constructs a filter configuration with a desired false-positive probability (`p`) and the
         * specified number of bits (`m`) and hash functions (`k`).
         *
         *
         * The number of items (`n`) to be stored in the filter is computed.
         * <pre>n = ceil(m / (-k / ln(1 - exp(ln(p) / k))))</pre>
         *
         *
         * The actual probability will be approximately equal to the
         * desired probability but will be dependent upon the calculated Bloom filter capacity
         * (number of items). An exception is raised if this is greater than or equal to 1 (i.e. the
         * shape is invalid for use as a Bloom filter).
         *
         * @param probability The desired false-positive probability in the range `(0, 1)`
         * @param numberOfBits The number of bits in the filter
         * @param numberOfHashFunctions The number of hash functions in the filter
         * @return a valid Shape.
         * @throws IllegalArgumentException if the desired probability is not in the range `(0, 1)`,
         * `numberOfBits < 1`, `numberOfHashFunctions < 1`, or the actual
         * probability is `>= 1.0`
         */
        fun fromPMK(probability: Double, numberOfBits: Int, numberOfHashFunctions: Int): Shape {
            checkProbability(probability)
            checkNumberOfBits(numberOfBits)
            checkNumberOfHashFunctions(numberOfHashFunctions)

            // Number of items (n):
            // n = ceil(m / (-k / ln(1 - exp(ln(p) / k))))
            val n = ceil(numberOfBits / (-numberOfHashFunctions / ln(-expm1(ln(probability) / numberOfHashFunctions))))

            // log of probability is always < 0
            // number of hash functions is >= 1
            // e^x where x < 0 = [0,1)
            // log 1-e^x = [log1, log0) = <0 with an effective lower limit of -53
            // numberOfBits/ (-numberOfHashFunctions / [-53,0) ) >0
            // ceil( >0 ) >= 1
            // so we cannot produce a negative value thus we don't check for it.
            //
            // similarly we cannot produce a number greater than numberOfBits so we
            // do not have to check for Integer.MAX_VALUE either.
            val shape = Shape(numberOfHashFunctions, numberOfBits)
            // check that probability is within range
            checkCalculatedProbability(shape.getProbability(n.toInt()))
            return shape
        }
    }
}
